In recent years, many vehicles are provided with a navigation apparatus that provides travel guidance for the vehicle to allow a driver to easily reach a desired destination location. The navigation apparatus is a device that can detect the current position of the vehicle using a GPS receiver or the like and acquire map data corresponding to the current position from a storage medium such as a DVD-ROM or an HDD or through a network to display the map data on a liquid crystal monitor. Furthermore, such a navigation apparatus is provided with a route search function for searching for an optimum route from the vehicle position to a desired destination location when the destination location is input, and adapted to set the optimum route found in the search as a route for guidance, display the route for guidance on a display screen, and provide audio guidance in the case where the vehicle approaches an intersection or the like in order to reliably guide a user to the desired destination location. In recent years, in addition, some cellular phones, smartphones, tablet terminals, personal computers, and so forth also have a function that is similar to that of the navigation apparatus described above.
For the route search function described above, a Dijkstra's algorithm is generally used as a route search method for searching for a route from a departure location to a destination location. In the Dijkstra's algorithm, a search cost (link cost, intersection cost) is calculated for each link included in the route and each node corresponding to an intersection, and an optimum route is specified on the basis of the sum of the calculated search costs. The search cost is also calculated on the basis of various parameters such as the average travel time, which is the average value of times required for vehicles to pass through a link, and the congestion degree, which indicates the degree of congestion of a link. The average travel time and the degree of congestion are specified by a server by statistically processing probe information and information (hereinafter referred to as calculation material information) collected by vehicle detectors, optical beacons, and so forth installed on roads, for example, as described in Japanese Patent Application Publication No. 2007-71579 (JP 2007-71579 A).